public class KnapsackBackTrackTest 
{
    public static void main(String [] args)
    {
        int w[]={2,2,6,5,4};
        int v[]={6,3,5,4,6};
        int W0=10;
        KnapsackBackTrack ks=new KnapsackBackTrack(w, v, W0);
        ks.solve();
    }
}
 class KnapsackBackTrack
{
    int w[];//重量
    int v[];//价值
    int W;//限重
    int bestvalue;
    int currentweight;
    int currentvalue;
    int currentchoise[];
    int bestchoise[];
    public KnapsackBackTrack(int w0[],int v0[],int W0)
    {
        w=w0;
        v=v0;
        W=W0;
        bestvalue=0;
        currentvalue=0;
        currentweight=0;
        currentchoise=new int[w.length];
        bestchoise=new int[w.length];
    }
    private void BackTrack(int depth)
    {
        if(depth>w.length-1)
        {
            if(bestvalue<currentvalue)
            {
                bestvalue=currentvalue;
                for(int i=0;i<currentchoise.length;i++)
                {
                    bestchoise[i]=currentchoise[i];
                }
            }
            return ;
        }
        if(currentweight+w[depth]<=W)
        {
            currentweight+=w[depth];
            currentvalue+=v[depth];
            currentchoise[depth]=1;
            BackTrack(depth+1);
            currentweight-=w[depth];
            currentvalue-=v[depth];
            currentchoise[depth]=0;

        }
        BackTrack(depth+1);

    }
    public void solve()
    {
        BackTrack(0);
        System.out.printf("最大价值:%d\n",bestvalue);
        System.out.printf("选择的物品:\n");
        for (int i=0;i<bestchoise.length;i++)
        {
            if(bestchoise[i]==1)
            {
                System.out.printf("%d ",i+1);
            }
        }
        System.out.println();
    }

    

}